[1]:

%run ../initscript.py
HTML("""
<div id="popup" style="padding-bottom:5px; display:none;">
    <div>Enter Password:</div>
    <input id="password" type="password"/>
    <button onclick="done()" style="border-radius: 12px;">Submit</button>
</div>
<button onclick="unlock()" style="border-radius: 12px;">Unclock</button>
<a href="#" onclick="code_toggle(this); return false;">show code</a>
""")

[1]:
show code
[2]:

%run ./loadoptfuncs.py
%matplotlib inline
toggle()

[2]:
show code

Linear Programming

All optimization models have several common elements:

  • Decision variables the variable whose values the decision maker is allowed to choose. The values of these variables determine such outputs as total cost, revenue, and profit.

  • An objective function (objective, for short) to be optimized – minimized or maximized.

  • Constraints that must be satisfied. They are usually physical, logical, or economic restrictions, depending on the nature of the problem.

    • In searching for the values of the decision variables that optimize the objective, only those values that satisfy all of the constraints are allowed.

To optimize means that you must systematically choose the values of the decision variables that make the objective as large (for maximization) or small (for minimization) as possible and cause all of the constraints to be satisfied.

Any set of values of the decision variables that satisfies all of the constraints is called a feasible solution. The set of all feasible solutions is called the feasible region.

As one of the fundamental prescriptive analysis method, linear programming (LP) is used in all types of organizations, often on a daily basis, to solve a wide variety of problems. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and/or linear inequality constraints.

A PC manufacturer assembles and then tests two models of computers, Basic and XP. There are at most 10,000 assembly hours at the cost of $11 available and 3000 testing hours at the cost of $15 available.

data ds_labor;
    input type $ cost avail;
    datalines;
    assemble 11 10000
        test 15 3000
;
run;

For each model, it has required assembly, testing hours, cost, price and estimated maximal sales.

data ds_model;
    input model $ assemble test cost price max_sale;
    datalines;
    Basic 5 1 150 300 600
       XP 6 2 225 450 1200
;
run;

Business assumptions: - No computers are in inventory from the previous period (or no beginning inventory) - Because these models are going to be changed after this month, the company doesn’t want to hold any inventory after this period (no ending inventory)

Business goal: the PC manufacturer wants to know - how many of each model it should produce - maximize its net profit

Business constraints: - resource constraints: available assembly and testing hours - market constraints: maximal sales

Modeling

The PC manufacturer wants to

\begin{align*} \text{maximize} \quad \text{Profit} &= \text{Basic's unit margin} \times \text{Production of Basic} \\ & \qquad \qquad+ \text{XP's unit margin} \times \text{Production of XP} \end{align*}

subject to following constraints: \begin{align*} &\text{assembly hours:} & 5 \times \text{Production of Basic} + 6 \times \text{Production of XP} &\le 10000 \\ &\text{testing hours:} & \text{Production of Basic} + 2\times \text{Production of XP} &\le 3000 \\ &\text{maximal sales:} & \text{Production of Basic} &\le 600 \\ &\text{maximal sales:} & \text{Production of XP} &\le 1200 \\ \end{align*}

Intuitive constraints: \begin{align*} \text{Production of Basic} &\ge 0 \\ \text{Production of XP} &\ge 0 \\ \end{align*}

Graphical solution

[3]:

interact(prodmix_graph,
         zoom=widgets.Checkbox(value=False, description='Zoom In', disabled=False));

[4]:

interact(prodmix_obj,
         zoom=widgets.Checkbox(value=False, description='Zoom In', disabled=False),
         margin1=widgets.IntSlider(min=-30,max=150,step=10,value=80,description='Margin Basic:',
                                   style = {'description_width': 'initial'}),
         margin2=widgets.IntSlider(min=-30,max=150,step=10,value=129,description='Margin XP:',
                                  style = {'description_width': 'initial'}));

Sensitivity Analysis

The sensitivity report from excel shows

Variable Cells

Cell

Name

Final Value

Reduced Cost

Objective Coefficient

Allowable Increase

Allowable Decrease

$B$16

Number to produce Basic

560

0

80

27.5

80

$C$16

Number to produce XP

1200

33

129

1E+30

33

  • Final Value: the optimal solution

  • Reduced Cost: it is relevant only if the final value is equal to either 0 or its upper bound. It indicates how much the objective coefficient of a decision variable (which is currently 0 or at its upper bound) must change before that variable changes. For example:

    • the number of XPs will stay at 1200 unless the profit margin for XPs decreases by at least $33

  • Allowable Increase/Decrease: it indicates how much the objective coefficient could change before the optimal solution would change. For example:

    • if the selling price of Basics stays within a range from $220 to $327.5, the optimal product mix does not change at all.

Constraints

Cell

Name

Final Value

Shadow Price

Constraint R.H. Side

Allowable Increase

Allowable Decrease

$B$21

Labor availability for assembling Hours used

10000

16

10000

200

2800

$B$22

Labor availability for testing Hours used

2960

0

3000

1E+30

40

  • Final Value: the value of the left side of the constraint at the optimal solution

  • Shadow Price: it indicates the change in the optimal value of the objective when the right side of some constraint changes by one unit. For example:

    • If the right side of this constraint increases by one hour, from 10000 to 10001, the optimal value of the objective will increase by $16.

SAS On Demand

  1. Go to the link and click “Not registered or cannot sign in?”

  2. Click “Don’t have a SAS Profile?”

  3. Register a SAS account and login

  4. Select enrollment tab and click “+ enroll in a course”

  5. The course code is: d66f5458-24ac-44b3-8733-13f3ec9f3822

SAS proc optmodel

proc optmodel;
/*read in data to set and arrays */
    set<str> LABORS;
    num cost{LABORS}, avail{LABORS};
    read data ds_labor into LABORS=[type] cost avail;

    set<str> MODELS;
    num price{MODELS}, hours{MODELS,LABORS}, mdl_cost{MODELS}, max_sale{MODELS};
    read data ds_model into MODELS=[model] {l in LABORS}<hours[model,l]=col(l)> mdl_cost=cost price max_sale;

    num margin{i in MODELS}
        = price[i] - mdl_cost[i] - sum{l in LABORS} cost[l] * hours[i,l];

/* *** build model *** */
    var Produce{i in MODELS} >=0;

    con Maximal_Sales{i in MODELS}:
        Produce[i] <= max_sale[i];

    con Avail_Labor{l in LABORS}:
        sum{i in MODELS} hours[i,l]*Produce[i] <= avail[l];

    max Profit=sum{i in MODELS} margin[i] * Produce[i];

    solve;

    create data solution from [i]=MODELS Produce[i];
quit;

Comparing to spreadsheet modeling, SAS modeling language allows user to separate modeling and solution reporting from data management.

data ds_labor;
    input type $ cost avail;
    datalines;
    assemble 11 20000
    test1    19 5000
    test2    17 6000
;
run;

data ds_model;
    input model $ assemble test1 test2 cost price max_sale;
    datalines;
    Model1 4   1.5 2   150 350 1500
    Model2 5   2   2.5 225 450 1250
    Model3 5   2   2.5 225 460 1250
    Model4 5   2   2.5 225 470 1250
    Model5 5.5 2.5 3   250 500 1000
    Model6 5.5 2.5 3   250 525 1000
    Model7 5.5 2.5 3.5 250 530 1000
    Model8 6   3   3.5 300 600 800
;
run;

proc optmodel;
/*read in data to set and arrays */
    set<str> LABORS;
    num cost{LABORS}, avail{LABORS};
    read data ds_labor into LABORS=[type] cost avail;

    set TESTS = {l in LABORS: find(l,'test')>0};

    set<str> MODELS;
    num price{MODELS}, hours{MODELS, LABORS}, mdl_cost{MODELS}, max_sale{MODELS};
    read data ds_model into MODELS=[model] {l in LABORS}<hours[model,l]=col(l)> mdl_cost=cost price max_sale;

    num margin{i in MODELS, t in TESTS}
        = price[i] - mdl_cost[i] - sum{l in LABORS: l='assemble' or l=t} cost[l] * hours[i,l];

/* *** build model *** */
    var Produce{i in MODELS, t in TESTS} >=0;

    con Maximal_Sales{i in MODELS}:
        sum{t in TESTS} Produce[i,t] <= max_sale[i];

    con Avail_Assemble{l in LABORS: l='assemble'}:
        sum{i in MODELS} (hours[i,l]*sum{t in TESTS} Produce[i,t]) <= avail[l];

    con Avail_Test{l in LABORS: find(l,'test')>0}:
            sum{i in MODELS} hours[i,l]*Produce[i,l] <= avail[l];

    max Profit=sum{i in MODELS, t in TESTS} margin[i,t] * Produce[i,t];

    solve;

    create data solution from [t]=TESTS {m in MODELS}<col(m)=Produce[m,t]>;
quit;